The provision of computing services in a multi-tenant environment may involve the storage and retrieval of large quantities of data. A variety of approaches may be employed. Typically, these may involve the use of relational or non-relational database or various ad hoc approaches. Relational databases, such as those that permit the storage and retrieval of data using a structured query language (“SQL”) may be suitable in various instances, particularly those where the data is highly structured and where data consistency is of high importance. Non-relational databases, such as those based on key-value storage, may be suitable where scalability is of greater importance than data consistency. However, each of these approaches has various drawbacks that may limit their usefulness in certain scenarios. One such scenario may, in general terms, involve the storage and retrieval of numerous pieces of unstructured data by a variety of applications and application instances, as might be seen in a multi-tenant environment. For example, the storage and retrieval of data related to various performance or usage metrics may not be well-suited for conventional storage approaches using relational or non-relational databases.